#include <stdio.h>
#include <stdbool.h>

void print(int array[], int n);

/* 冒泡排序 */
void bubbleSort(int array[], int n);

/* 插入排序 */
void insertionSort(int array[], int n);

/* 选择排序 */
void selectionSort(int array[], int n);

/* 归并排序 */
void mergeSort(int array[], int n);
void mergeSort0(int array[], int start, int end);

/* 快速排序 */
void quickSort(int array[], int n);
void quickSort0(int array[], int start, int end);
int partition(int array[], int start, int end);

void main()
{
    // int array[] = {4, 5, 6, 3, 2, 1};
    int array[] = {6, 5, 4, 3, 2, 1};
    int len = 6;
    // int array[] = {4, 2, 1};

    // bubbleSort(array, 6);

    // insertionSort(array, 3);

    // selectionSort(array, len);

    // mergeSort(array, len);

    quickSort(array, len);

    print(array, len);
}

void print(int array[], int n)
{
    for (int i = 0; i < n; i++)
    {
        printf("%d\n", array[i]);
    }
}

/*
    冒泡排序
        1. 冒泡的过程只涉及相邻数据的交换操作，只需要常量级的临时空间，所以它的空间复杂度为 O(1)，是一个原地排序算法。
        2. 在冒泡排序中，只有交换才可以改变两个元素的前后顺序。为了保证冒泡排序算法的稳定性，当有相邻的两个元素大小相等的时候，我们不做交换，相同大小的数据在排序前后不会改变顺序，所以冒泡排序是稳定的排序算法。
        3. 最好情况下，要排序的数据已经是有序的了，我们只需要进行一次冒泡操作，就可以结束了，所以最好情况时间复杂度是 O(n)。而最坏的情况是，要排序的数据刚好是倒序排列的，我们需要进行 n 次冒泡操作，所以最坏情况时间复杂度为 O(n^2)。
*/
void bubbleSort(int array[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        bool flag = false;
        for (int j = 0; j < n - 1 - i; j++)
        {
            if (array[j] > array[j + 1])
            {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
                flag = true;
            }
        }
        if (flag == false)
        {
            break;
        }
    }
}

/*
    插入排序
        1. 从实现过程可以很明显地看出，插入排序算法的运行并不需要额外的存储空间，所以空间复杂度是 O(1)，也就是说，这是一个原地排序算法。
        2. 在插入排序中，对于值相同的元素，我们可以选择将后面出现的元素，插入到前面出现元素的后面，这样就可以保持原有的前后顺序不变，所以插入排序是稳定的排序算法。
        3. 在数组中插入一个数据的平均时间复杂度是 O(n)。所以，对于插入排序来说，每次插入操作都相当于在数组中插入一个数据，循环执行 n 次插入操作，所以平均时间复杂度为 O(n2)。
 */
void insertionSort(int array[], int n)
{
    for (int i = 1; i < n; i++)
    {
        int value = array[i];
        int j = i - 1;
        for (; j >= 0; j--)
        {
            if (array[j] > value)
            {
                array[j + 1] = array[j];
            }
            else
            {
                break;
            }
        }
        array[j + 1] = value;
    }
}

/*
    选择排序
        1. 首先，选择排序空间复杂度为 O(1)，是一种原地排序算法。
        2. 选择排序的最好情况时间复杂度、最坏情况和平均情况时间复杂度都为 O(n2)。
        3. 选择排序是一种不稳定的排序算法。选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。
*/
void selectionSort(int array[], int n)
{
    for (int i = 0; i < n - 1; i++)
    {
        int max = array[i];
        int index = i;
        for (int j = i + 1; j < n; j++)
        {
            if (array[j] < max)
            {
                max = array[j];
                index = j;
            }
        }
        array[index] = array[i];
        array[i] = max;
    }
}

/*
    归并排序
        1. 在合并的过程中，如果 A[p...q]和 A[q+1...r]之间有值相同的元素，那我们可以像伪代码中那样，先把 A[p...q]中的元素放入 tmp 数组。这样就保证了值相同的元素，在合并前后的先后顺序不变。所以，归并排序是一个稳定的排序算法。
        2. 归并排序的时间复杂度是 O(nlogn)。
        3. 由于要创建临时数组存放排序好的部分元素，所以空间复杂度是 O(n)。
*/
void mergeSort(int array[], int n)
{
    mergeSort0(array, 0, n - 1);
}

void mergeSort0(int array[], int start, int end)
{
    if (start >= end)
        return;

    // 数组中间点下标
    int q = (start + end) / 2;

    mergeSort0(array, start, q);
    mergeSort0(array, q + 1, end);

    int temp[start + end + 1];
    int i = start, j = q + 1, k = 0;

    while (i <= q && j <= end)
    {
        if (array[i] <= array[j])
        {
            temp[k++] = array[i++];
        }
        else
        {
            temp[k++] = array[j++];
        }
    }

    int start0 = i, end0 = q;
    if (j <= end)
    {
        start0 = j;
        end0 = end;
    }

    while (start0 <= end0)
    {
        temp[k++] = array[start0++];
    }

    for (int i = 0; i <= end - start; i++)
    {
        array[start + i] = temp[i];
    }
}

/*
    快速排序
        1. 快排是一种原地、不稳定的排序算法。
        2. 归并排序的时间复杂度是 O(nlogn)。
*/
void quickSort(int array[], int n)
{
    quickSort0(array, 0, n - 1);
}

void quickSort0(int array[], int start, int end)
{
    if (start >= end)
        return;

    int q = partition(array, start, end);
    quickSort0(array, start, q - 1);
    quickSort0(array, q + 1, end);
}

int partition(int array[], int start, int end)
{
    int pivot = array[end];
    int i = start;

    for (int j = start; j < end; j++)
    {
        if (array[j] < pivot)
        {
            int temp = array[j];
            array[j] = array[i];
            array[i] = temp;
            i++;
        }
    }
    array[end] = array[i];
    array[i] = pivot;
    return i;
}